//https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/description/?envType=daily-question&envId=2023-11-01


class Solution {
public:
    vector<int>d;
    vector<vector<int>>g;
    vector<vector<int>>h;
    vector<bool>st;
    int cnt1;
    int dfs(int u, int fa, int&k){
        int sum = 1;
        st[u] = true;
        for(auto c : g[u]){
            if(c != fa && d[c]!= 0 && !st[c]){
                k = c;
                sum += dfs(c, u, k);
            }
        }
        return sum;
    }
    void dfs2(int u, int fa, int sum){
        cnt1 = max(cnt1, sum);
        st[u] = true;
        for(auto c : g[u]){
            if(c != fa && !st[c] && d[c] == 0){
                sum++;
                dfs2(c, u, sum);
                sum--;
            }
        }
    }

    int maximumInvitations(vector<int>& favorite) {
        int n = favorite.size();
        d.resize(n);
        g.resize(n);
        h.resize(n);
        st.resize(n);
        for(int i = 0; i < favorite.size(); i++){
            d[favorite[i]]++;
            h[i].push_back(favorite[i]);
            g[favorite[i]].push_back(i);
            g[i].push_back(favorite[i]);
        }
        queue<int>q;
        for(int i = 0; i < favorite.size(); i++)if(d[i] == 0)q.push(i);
        while(q.size()){
            auto t = q.front();
            q.pop();
            for(auto c : h[t]){
                d[c]--;
                if(d[c] == 0)q.push(c);
            }
        }
        int res = 0;
        int cnttwo = 0;
        int ans = 0;
        for(int i = 0; i < favorite.size(); i++){
            if(d[i] != 0 && !st[i]){
                int v = -1;
                int sum = dfs(i, -1, v);
                if(sum == 2){  
                    cnttwo++;
                    int t = 0;
                    cnt1 = 0;
                    dfs2(i, -1, 0);
                    t += cnt1;
                    cnt1 = 0;
                    dfs2(v, -1, 0);
                    t += cnt1;
                    ans += t;
                }
                else {
                    res = max(res, sum);
                }
            }
            if(d[i] != 0){
                dfs2(i, -1, 0);
            }
        }
        res = max(res, cnttwo * 2 + ans);
        return res;
    }
};
